use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]; // right, down, left, up
    let rows = maze.len();
    let cols = maze[0].len();
    let mut queue = VecDeque::new();
    queue.push_back((start, vec![start]));
    let mut visited = vec![vec![false; cols]; rows];
    visited[start.0][start.1] = true;
    while let Some((current, path)) = queue.pop_front() {
        // this exist a step compare, all bifurcation point will run same circle, the one win when it find end first.
        let (x, y) = current;
        // If we've reached the end, return the path
        if current == end {
            return path;
        }
        // Check all 4 possible directions
        for &(dx, dy) in &directions {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            // Ensure the next position is within bounds and not a wall, and hasn't been visited
            if nx >= 0 && ny >= 0 && nx < rows as isize && ny < cols as isize {
                let nx = nx as usize;
                let ny = ny as usize;
                if !visited[nx][ny] && maze[nx][ny] != '#' {
                    visited[nx][ny] = true;
                    let mut new_path = path.clone();
                    new_path.push((nx, ny));
                    queue.push_back(((nx, ny), new_path));
                }
            }
        }
        println!("{:?}", queue);
    }
    // If no path is found, return an empty vector
    vec![]
}
